Primitive Polynomial (field Theory)

In finite field theory, a branch of mathematics, a primitive polynomial is the minimal polynomial of a primitive element of the finite field . This means that a polynomial of degree with coefficients in is a ''primitive polynomial'' if it has a root in such that is the entire field . This implies that is a primitive ()-root of unity in .

Properties

* Because all minimal polynomials are irreducible, all primitive polynomials are also irreducible.

* A primitive polynomial must have a non-zero constant term, for otherwise it will be divisible by ''x''. Over GF(2), is a primitive polynomial and all other primitive polynomials have an odd number of terms, since any polynomial mod 2 with an even number of terms is divisible by (it has 1 as a root).

* An irreducible polynomial ''F''(''x'') of degree ''m'' over GF(''p''), where ''p'' is prime, is a primitive polynomial if the smallest positive integer ''n'' such that ''F''(''x'') divides is .

* Over GF(''p''^''m'') there are exactly primitive polynomials of degree ''m'', where ''φ'' is Euler's totient function.

* A primitive polynomial of degree ''m'' has ''m'' different roots in GF(''p''^''m''), which all have order . This means that, if ''α'' is such a root, then and for .

* The primitive polynomial ''F''(''x'') of degree ''m'' of a primitive element ''α'' in GF(''p''^''m'') has explicit form .

Usage

Field element representation

Primitive polynomials can be used to represent the elements of a finite field. If ''α'' in GF(''p''^''m'') is a root of a primitive polynomial ''F''(''x''), then the nonzero elements of GF(''p''^''m'') are represented as successive powers of ''α'':

:$\mathrm(p^m) = \ .$

This allows an economical representation in a computer of the nonzero elements of the finite field, by representing an element by the corresponding exponent of $\alpha.$ This representation makes multiplication easy, as it corresponds to addition of exponents modulo $p^m-1.$

Pseudo-random bit generation

Primitive polynomials over GF(2), the field with two elements, can be used for pseudorandom bit generation. In fact, every linear-feedback shift register with maximum cycle length (which is , where ''n'' is the length of the linear-feedback shift register) may be built from a primitive polynomial.

In general, for a primitive polynomial of degree ''m'' over GF(2), this process will generate pseudo-random bits before repeating the same sequence.

CRC codes

The cyclic redundancy check (CRC) is an error-detection code that operates by interpreting the message bitstring as the coefficients of a polynomial over GF(2) and dividing it by a fixed generator polynomial also over GF(2); see Mathematics of CRC. Primitive polynomials, or multiples of them, are sometimes a good choice for generator polynomials because they can reliably detect two bit errors that occur far apart in the message bitstring, up to a distance of for a degree ''n'' primitive polynomial.

Primitive trinomials

A useful class of primitive polynomials is the primitive trinomials, those having only three nonzero terms: . Their simplicity makes for particularly small and fast linear-feedback shift registers. A number of results give techniques for locating and testing primitiveness of trinomials.

For polynomials over GF(2), where is a Mersenne prime, a polynomial of degree ''r'' is primitive if and only if it is irreducible. (Given an irreducible polynomial, it is ''not'' primitive only if the period of ''x'' is a non-trivial factor of . Primes have no non-trivial factors.) Although the Mersenne Twister pseudo-random number generator does not use a trinomial, it does take advantage of this.

Richard Brent has been tabulating primitive trinomials of this form, such as . This can be used to create a pseudo-random number generator of the huge period ≈ .

References

External links

* {{MathWorld , urlname=PrimitivePolynomial , title=Primitive Polynomial

Field (mathematics)
Polynomials